package algorithm_demo.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 40. 组合总和 II
 * <a href="https://leetcode.cn/problems/combination-sum-ii/">https://leetcode.cn/problems/combination-sum-ii/</a>
 * @author Api
 * @date 2023/5/6 22:34
 */
public class Problem_040_CombinationSumII {
    List<List<Integer>> list2 = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if (candidates.length == 0){
            return list2;
        }
        boolean[] used = new boolean[candidates.length];
        List<Integer> path = new ArrayList<>();
        Arrays.sort(candidates);
        dfs(candidates, 0, 0, target, used, path);
        return list2;
    }


    public void dfs(int[] nums, int start, int sum, int target, boolean[] used, List<Integer> path){
        if (sum == target){
            list2.add(new ArrayList<>(path));
            return;
        }
        //剪枝3：sum+nums[i]<=target,在找到大于target那个分支之后，这nums.length分支后面的就不用看了，肯定大于
        //剪枝4：:123和132是一个答案，后面的132要被去掉，通过i=start来实现，因为下一层只能比上一层的值更大不能更小
        for(int i = start; i<nums.length&&sum+nums[i]<=target;i++){
            if(used[i] == true){
                continue;
            }
            if (i>0 && nums[i] == nums[i-1] && used[i-1] == false){
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            dfs(nums, i, sum+nums[i], target, used, path);
            path.remove(path.size()-1);
            used[i] = false;
        }
    }
}
